namespace DataStructure
{
    /// <summary>
    /// 左倾红黑树
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public class RBT2<Key,Value> where Key : IComparable<Key>
    {
        private const bool Red = true;
        private const bool Black = false;
        public class Node
        {
            public Key key;
            public Value value;
            public Node left;
            public Node right;
            public bool color;
            
            public Node(Key key, Value value)
            {
                this.key = key;
                this.value = value;
                left = null;
                right = null;
                color = Red; //默认为红色
            }
        }
        
        private Node root;
        private int count;
        
        public RBT2()
        {
            root = null;
            count = 0;
        }
        
        public int Count => count;
        public bool IsEmpty => count == 0;
        
        private bool IsRed(Node node)
        {
            if (node == null)
                return Black;
            return node.color;
        }
        //颜色反转
        private void FilpColors(Node node)
        {
            node.color = Red;
            node.left.color = Black;
            node.right.color = Black;
        }
        
        //左旋转
        private Node LeftRotate(Node node)
        {
            Node x = node.right;
            node.right = x.left;
            x.left = node;
            x.color = node.color;
            node.color = Red;
            
            return x;
        }
        
        //右旋转
        private Node RightRotate(Node node)
        {
            Node x = node.left;
            node.left = x.right;
            x.right = node;
            x.color = node.color;
            node.color = Red;

            return x;
        }
        
        //往红黑树中添加元素
        public void Add(Key key, Value value)
        {
            root = Add(root, key, value);
            root.color = Black;
        }
        private Node Add(Node node, Key key, Value value)
        {
            if (node == null)
            {
                count++;
                return new Node(key, value);//默认红节点
            }
            if(key.CompareTo(node.key) < 0)
                node.left = Add(node.left,key,value);
            else if(key.CompareTo(node.key) > 0)
                node.right = Add(node.right,key,value);
            else
                node.value = value;
                
            //右子节点是红色，左子节点是黑色，左旋转
            if(IsRed(node.right) && !IsRed(node.left))
                node = LeftRotate(node);
            //左子节点是红色，左子节点的左子节点也是红色，右旋转
            if (IsRed(node.left) && IsRed(node.left.left))
                node = RightRotate(node);
            //左右子节点都是红色，颜色反转
            if (IsRed(node.left) && IsRed(node.right))
                FilpColors(node);
                
            return node;
        }
        
        private Node GetNode(Node node, Key key)
        {
            if (node == null)
                return null;
                
            if(key.Equals(node.key))
                return node;
            else if (key.CompareTo(node.key) < 0)
                return GetNode(node.left, key);
            else
                return GetNode(node.right, key);
        }
        
        public bool Contains(Key key)
        {
            return GetNode(root, key) != null;
        }
        
        public Value Get(Key key)
        {

            Node node = GetNode(root, key);
            if (node == null)
                throw new ArgumentException("键" + key + "不存在，无法获取对应值");
            else
                return node.value;
        }
        
        public void Set(Key key, Value newValue)
        {
            Node node = GetNode(root, key);
            
            if(node == null)
                throw new ArgumentException("键" + key + "不存在，无法设置对应值");
            else
                node.value = newValue;
        }
        
        //最大高度
        public int MaxHeight()
        {
            return MaxHeight(root);
        }

        private int MaxHeight(Node node)
        {
            if (node == null)
                return 0;
            
            return Math.Max(MaxHeight(node.left), MaxHeight(node.right)) + 1;
        }
        //TODO:删除节点
    }
}